{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Equal Frequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxEqualFreq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大相等频率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>nums</code>，请你帮忙从该数组中找出能满足下面要求的 <strong>最长</strong> 前缀，并返回该前缀的长度：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从前缀中 <strong>恰好删除一个</strong> 元素后，剩下每个数字的出现次数都相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,1,1,5,3,3,5]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]\n",
    "<strong>输出：</strong>13\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-equal-frequency](https://leetcode.cn/problems/maximum-equal-frequency/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-equal-frequency](https://leetcode.cn/problems/maximum-equal-frequency/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,1,1,5,3,3,5]', '[1,1,1,2,2,2,3,3,3,4,4,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        f = Counter()\n",
    "        n = len(nums)\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            if cnt[x] != 1:\n",
    "                f[cnt[x] - 1] -= 1\n",
    "            f[cnt[x]] += 1\n",
    "            mx = max(mx, cnt[x])\n",
    "            if mx == 1 or (f[mx] * mx + f[mx - 1] * (mx - 1) == i + 1 and f[mx] == 1) or (f[mx] * mx + 1 == i + 1 and f[1] == 1):\n",
    "                ans = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        freq = Counter(cnt.values())\n",
    "\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            if len(cnt) == 1:\n",
    "                return i + 1\n",
    "            if len(freq) == 1 and 1 in freq:\n",
    "                return i + 1\n",
    "            if len(freq) == 2:\n",
    "                x, y = min(freq), max(freq)\n",
    "                if x == 1 and freq[x] == 1 or y == x + 1 and freq[y] == 1:\n",
    "                    return i + 1\n",
    "            \n",
    "            f = cnt[nums[i]]\n",
    "            if f > 1:\n",
    "                cnt[nums[i]] = f - 1\n",
    "                freq[f-1] += 1\n",
    "            else:\n",
    "                del cnt[nums[i]]\n",
    "            \n",
    "            freq[f] -= 1\n",
    "            if freq[f] == 0:\n",
    "                del freq[f]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        删除一个元素后频次相同有以下几种情况:\n",
    "        1. 每个数只出现一次\n",
    "        2. 只有一个数比其他数出现多一次，其他数一样多 (删掉多一次的一个数)\n",
    "        3. 大家都出现的一样多，只有一个数出现了一次 (删掉一次的这个数)\n",
    "        那么怎么维护从头开始的个数，方便统计这三个条件呢？\n",
    "        哈希表记录次数是肯定的\n",
    "        1. 都是一个数，说明最大长度是1\n",
    "        2. 需要统计出现的个数的个数才好确定后两种情况\n",
    "        \"\"\"\n",
    "        counter, counter_counter, max_counts, ans = Counter(), Counter(), 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if counter[num]:\n",
    "                counter_counter[counter[num]] -= 1\n",
    "            counter[num] += 1\n",
    "            counter_counter[counter[num]] += 1\n",
    "            if counter[num] > max_counts:\n",
    "                max_counts = counter[num]\n",
    "            if max_counts == 1 or (counter_counter[max_counts - 1] + 1) * (max_counts - 1) == i or max_counts * counter_counter[max_counts] == i:\n",
    "                ans = i + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # freq = num2freq[num]: 元素 num 出现的次数\n",
    "        # cnt = freq2cnt[freq]: 出现次数为 freq 的元素个数\n",
    "        num2freq = Counter()\n",
    "        freq2cnt = Counter()\n",
    "\n",
    "        res, max_freq = 0, 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num2freq[num] > 0:\n",
    "                freq2cnt[num2freq[num]] -= 1\n",
    "\n",
    "            num2freq[num] += 1\n",
    "            max_freq = max(max_freq, num2freq[num])\n",
    "            freq2cnt[num2freq[num]] += 1\n",
    "\n",
    "            # CASE1: 所有元素出现次数均为 1\n",
    "            cond1 = max_freq == 1\n",
    "            # CASE2: 出现次数为 1 的元素只有一个，其余元素出现次数均相等\n",
    "            cond2 = (freq2cnt[1] == 1 and freq2cnt[max_freq] * max_freq == i)\n",
    "            # CASE3：出现最多的元素只有一个，其余元素出现次数均相等，且出现次数比最大次数少一\n",
    "            cond3 = (freq2cnt[max_freq] == 1 and (\n",
    "                max_freq + freq2cnt[max_freq - 1] * (max_freq - 1) == i + 1))\n",
    "            \n",
    "            if cond1 or cond2 or cond3:\n",
    "                res = i + 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        c = Counter() # 统计每个元素的出现次数\n",
    "        cc = Counter() # 统计每个出现次数有多少种元素\n",
    "        ans = 0\n",
    "        max_f = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if c[x] > 0:\n",
    "                cc[c[x]] -= 1\n",
    "            c[x] += 1\n",
    "            cc[c[x]] += 1\n",
    "            max_f = max(max_f, c[x])\n",
    "            if max_f == 1 or cc[max_f] == 1 and max_f + cc[max_f - 1] * (max_f - 1) == i + 1 or cc[max_f] * max_f + 1 == i + 1 and cc[1] == 1:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        freq = Counter()\n",
    "        ans = 1\n",
    "        for i, num in enumerate(nums):\n",
    "            if cnt[num]:\n",
    "                freq[cnt[num]] -= 1\n",
    "                if not freq[cnt[num]]:\n",
    "                    del freq[cnt[num]]\n",
    "            cnt[num] += 1\n",
    "            freq[cnt[num]] += 1\n",
    "            if len(freq) == 1 and (cnt[num] == 1 or len(cnt) == 1):\n",
    "                ans = max(ans, i + 1)\n",
    "            elif len(freq) == 2:\n",
    "                a, b = sorted(list(freq.keys()))\n",
    "                if (1 in (a, b) and freq[1] == 1) or (b - a == 1 and freq[b] == 1):\n",
    "                    ans = max(ans, i + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        curr_max, curr_max_count = -1, -1\n",
    "        count = defaultdict(int)\n",
    "        result = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            # update count, curr_max, curr_max_count\n",
    "            count[num] += 1\n",
    "            if count[num] == curr_max:\n",
    "                curr_max_count += 1\n",
    "            elif count[num] > curr_max:\n",
    "                curr_max, curr_max_count = count[num], 1\n",
    "            # delete some element from curr_max?\n",
    "            if curr_max_count == 1 and (curr_max-1) * len(count) == i:\n",
    "                result = max(result, i+1)\n",
    "            # delete some element from the least class?\n",
    "            if (curr_max * curr_max_count == i and curr_max_count == len(count)-1) \\\n",
    "                or (curr_max == 1 and curr_max_count == i+1):\n",
    "                result = max(result, i+1)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        count, freq = Counter(), Counter()\n",
    "        ans, maxFreq = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if count[num]:\n",
    "                freq[count[num]] -= 1\n",
    "            count[num] += 1\n",
    "            freq[count[num]] += 1\n",
    "            maxFreq = max(maxFreq, count[num])\n",
    "            if maxFreq == 1 or freq[maxFreq] == 1 and freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 or freq[1] == 1 and freq[maxFreq] * maxFreq + 1 == i + 1:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        freq, count = Counter(), Counter()\n",
    "        ans = maxFreq = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if count[num]:\n",
    "                freq[count[num]] -= 1\n",
    "            count[num] += 1\n",
    "            maxFreq = max(maxFreq, count[num])\n",
    "            freq[count[num]] += 1\n",
    "            if maxFreq == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 and freq[maxFreq] == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + 1 == i + 1 and freq[1] == 1:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isLegal(counts,sum):\n",
    "    if len(counts)==sum or len(counts)+1==sum:\n",
    "        return True\n",
    "    if len(counts)==1:\n",
    "        return True\n",
    "    if len(counts)==2:\n",
    "        for num,cnt in counts.items():\n",
    "            if cnt==1:\n",
    "                return True\n",
    "    # 数字的数量必须%len(counts)==1或%(len(counts)-1)==1\n",
    "    result=True\n",
    "    if sum%(len(counts)-1)==1:\n",
    "        delete=False\n",
    "        aver=sum//(len(counts)-1)\n",
    "        for num,cnt in counts.items():\n",
    "            if cnt!=aver and cnt!=1:\n",
    "                result=False\n",
    "                break\n",
    "            if cnt==1:\n",
    "                if delete:\n",
    "                    result=False\n",
    "                    break\n",
    "                else:\n",
    "                    delete=True\n",
    "        if delete and result:\n",
    "            return True\n",
    "    if sum%len(counts)==1:\n",
    "        delete=False\n",
    "        aver=sum//len(counts)\n",
    "        for num,cnt in counts.items():\n",
    "            if cnt!=aver and cnt!=aver+1:\n",
    "                return False\n",
    "            if cnt==aver+1:\n",
    "                if delete:\n",
    "                    return False\n",
    "                else:\n",
    "                    delete=True\n",
    "        return delete\n",
    "    return False\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        counts={}\n",
    "        for num in nums:\n",
    "            counts[num]=counts.get(num,0)+1\n",
    "        if isLegal(counts,len(nums)):\n",
    "            return len(nums)\n",
    "        for i in range(0,len(nums)):\n",
    "            counts[nums[-i-1]]-=1\n",
    "            if counts[nums[-i-1]]==0:\n",
    "                counts.pop(nums[-i-1])\n",
    "            if isLegal(counts,len(nums)-i-1):\n",
    "                return len(nums)-i-1\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        freq = Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            freq[cnt[num]] -= 1\n",
    "            if freq[cnt[num]] <= 0:\n",
    "                del freq[cnt[num]]\n",
    "            cnt[num] += 1\n",
    "            freq[cnt[num]] += 1\n",
    "            if len(freq) == 2:\n",
    "                s = sorted(freq.items())\n",
    "                if s[0][0] == 1 and s[0][1] == 1 or s[1][0] == s[0][0] + 1 and s[1][1] == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "            if len(freq) == 1:\n",
    "                s = sorted(freq.items())\n",
    "                if s[0][0] == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "                if len(cnt) == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "            # print(freq)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        freq = Counter(cnt.values())\n",
    "\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            m = max(freq)\n",
    "            if m == 1 or m * freq[m] + 1 == i + 1 or (m-1) * (freq[m-1] + 1) + 1 == i + 1:\n",
    "                return i + 1\n",
    "            \n",
    "            f = cnt[nums[i]]\n",
    "            if f > 1:\n",
    "                cnt[nums[i]] = f - 1\n",
    "                freq[f-1] += 1\n",
    "            else:\n",
    "                del cnt[nums[i]]\n",
    "            \n",
    "            freq[f] -= 1\n",
    "            if freq[f] == 0:\n",
    "                del freq[f]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        if nums is None or len(nums) == 0:\n",
    "            return 0\n",
    "        \n",
    "        info1 = {}\n",
    "        info2 = {}\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if info1.get(nums[i], None) is None:\n",
    "                info1[nums[i]] = 1\n",
    "                info2[1] = info2.get(1, 0) + 1\n",
    "                remainder = (i % (len(info1) - 1))  if (len(info1) - 1) > 0 else 0\n",
    "                if remainder == 0:\n",
    "                    cnt = (i // (len(info1) - 1))  if (len(info1) - 1) > 0 else 0\n",
    "                    if info2.get(cnt, 0) == len(info1) - 1 or (cnt == 1 and info2[1] == len(info1)):\n",
    "                        res = i + 1\n",
    "                elif info2[1] == len(info1) - 1 and info2.get(2, 0) == 1:\n",
    "                    res = i + 1\n",
    "            else:\n",
    "                info2[info1[nums[i]]] -= 1\n",
    "                info1[nums[i]] += 1\n",
    "                info2[info1[nums[i]]] = info2.get(info1[nums[i]], 0 ) + 1\n",
    "\n",
    "                if info2[info1[nums[i]]] == len(info1) - 1:\n",
    "                    if info2.get(1, 0) == 1 or info2[info1[nums[i]] - 1] == len(info1) - 1 or info2.get(info1[nums[i]] + 1, 0) == 1:\n",
    "                        res = i + 1\n",
    "                elif info2[info1[nums[i]]] == 1 and info2[info1[nums[i]] - 1] == len(info1) - 1:\n",
    "                    res = i + 1\n",
    "\n",
    "                # elif info2[info1[nums[i]]] == len(info1) - 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        #时间复杂度小于n方\n",
    "        num_time = Counter()\n",
    "        time_fre = Counter()\n",
    "        max_fre = 0\n",
    "        ans = 0\n",
    "        for j,i in enumerate(nums):\n",
    "            if num_time[i]:\n",
    "                time_fre[num_time[i]] -= 1\n",
    "            num_time[i] += 1\n",
    "            time_fre[num_time[i]]+=1\n",
    "            max_fre = max(max_fre,num_time[i])\n",
    "            #判断什么时候需要更新\n",
    "            #删除最多的一个，或者删除最少的一个\n",
    "            if max_fre==1 or \\\n",
    "                max_fre*(time_fre[max_fre])+(max_fre-1)*time_fre[max_fre-1] ==j+1 and time_fre[max_fre]==1 or \\\n",
    "                max_fre*time_fre[max_fre]==j:\n",
    "                ans = max(ans,j+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        cnt=0\n",
    "        map1=defaultdict(int)\n",
    "        map2=defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            t1=map1[nums[i]]\n",
    "            map1[nums[i]]=t1+1\n",
    "            map2[t1]-=1\n",
    "            map2[t1+1]+=1\n",
    "            if map2[t1]==0:\n",
    "                cnt-=1\n",
    "            if map2[t1+1]==1:\n",
    "                cnt+=1\n",
    "            if cnt==1 and (map2[t1+1]==1 or map2[1]>0):\n",
    "                res+=1\n",
    "            if cnt!=2:\n",
    "                continue\n",
    "            if map2[t1]>0 and map2[t1+1]==1:\n",
    "                res=i+1\n",
    "            if map2[t1+1]>0 and map2[t1+2]==1:\n",
    "                res=i+1\n",
    "            if map2[1]==1:\n",
    "                res=i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = 1\n",
    "        dct = dict()\n",
    "        freq = dict()\n",
    "        for i in range(n):\n",
    "            dct[nums[i]] = dct.get(nums[i], 0) + 1\n",
    "            pre = dct[nums[i]] - 1\n",
    "            if pre:\n",
    "                freq[pre] -= 1\n",
    "                if not freq[pre]:\n",
    "                    del freq[pre]\n",
    "            freq[pre+1] = freq.get(pre+1, 0) + 1\n",
    "            if len(freq) == 1:\n",
    "                if 1 in freq:\n",
    "                    ans = i+1\n",
    "                else:\n",
    "                    k = list(freq.keys())[0]\n",
    "                    if freq[k] == 1:\n",
    "                        ans = i+1\n",
    "            elif len(freq) == 2:\n",
    "                if 1 in freq and freq[1] == 1:\n",
    "                    ans = i+1\n",
    "                else:\n",
    "                    a, b = sorted(freq.keys())\n",
    "                    if a == b-1 and freq[b] == 1:\n",
    "                        ans = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        if len(set(nums)) == 1:return len(nums)\n",
    "        ans = 1\n",
    "        c = Counter()\n",
    "        for i in range(len(nums)):\n",
    "            c[nums[i]] += 1\n",
    "            if (i % len(c) == 0 and min(c.values()) ==i//len(c)) or (len(c)>1 and i%(len(c)-1)==0 and min(c.values())==1 and max(c.values()) == i//(len(c)-1)):\n",
    "                ans = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        num_to_n={}\n",
    "        n_to_num={}\n",
    "        res = 1\n",
    "        for i,x in enumerate(nums):\n",
    "            n = num_to_n.get(x,0)\n",
    "            num_to_n[x] = n+1\n",
    "            n_to_num[n+1] = n_to_num.get(n+1,0)+1\n",
    "            if n:\n",
    "                if n_to_num[n]==1:\n",
    "                    del n_to_num[n]\n",
    "                else:\n",
    "                    n_to_num[n]-=1\n",
    "            #\n",
    "            if len(n_to_num) == 1 and (n_to_num[n+1]==1 or n==0):\n",
    "                res = i+1\n",
    "            #x是长的\n",
    "            elif len(n_to_num) == 2 and n in n_to_num and n_to_num[n+1]==1:\n",
    "                res = i+1\n",
    "            #x是短的\n",
    "            elif len(n_to_num) == 2 and  n_to_num.get(n+2,0)==1:\n",
    "                res = i+1\n",
    "            elif len(n_to_num) == 2 and n_to_num.get(1,0) == 1:\n",
    "                res = i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        c = collections.Counter(nums)\n",
    "        c_v = collections.Counter(c.values())\n",
    "        if len(c)==len(nums) or len(c)==1: return len(nums)\n",
    "        while nums:\n",
    "            if len(c_v)==2:\n",
    "                a, b = sorted(c_v.keys())\n",
    "                if (a==1 and c_v[1]==1) or (b-1==a and c_v[b]==1): return len(nums)\n",
    "            x = nums.pop()\n",
    "            c_v[c[x]] -= 1\n",
    "            if c_v[c[x]]==0: c_v.pop(c[x])\n",
    "            c[x] -= 1\n",
    "            if c[x]: c_v[c[x]] += 1\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # for i in range(n, 0, -1):\n",
    "        #     count = Counter(nums[:i])\n",
    "            \n",
    "        #     s = set()\n",
    "        #     for key, value in count.items():\n",
    "        #         s.add(value)\n",
    "            \n",
    "        #     if len(s) == 2 and (any(a == 1 for a in s) or abs(a - b)==1 for a, b in s):\n",
    "        #         return i \n",
    "        # return 0\n",
    "\n",
    "        freq, count = Counter(), Counter()\n",
    "        res = 1\n",
    "        maxFreq = 0\n",
    "        species = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if count[num] == 0:\n",
    "                species += 1\n",
    "            count[num] += 1\n",
    "            maxFreq = max(maxFreq, count[num])\n",
    "            freq[count[num]] += 1\n",
    "            freq[count[num] - 1] -= 1\n",
    "            if species == i + 1 or species == 1:        # 123456 111111\n",
    "                res = i + 1\n",
    "            if freq[maxFreq] == species - 1 and freq[1] == 1:    #111 222 333 4\n",
    "                res = i + 1\n",
    "            if freq[maxFreq] == 1 and freq[maxFreq - 1] == species - 1: #111 222 333 4444\n",
    "                res = i + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        def check(dd):\n",
    "            print(dd)\n",
    "            if len(dd)==1 and (1 in dd.values() or 1 in dd.keys()):\n",
    "                return True\n",
    "            if len(dd)>2:\n",
    "                return False\n",
    "            if dd[1]==1:\n",
    "                return True\n",
    "            if len(dd)==2:\n",
    "                a,b = list(dd.keys())\n",
    "                if b>a:\n",
    "                    a,b = b,a\n",
    "                if (a-b==1 and dd[a]==1) or (b==1 and dd[b]==1):\n",
    "                    return True\n",
    "            \n",
    "        d = Counter(nums)\n",
    "        dd = Counter(list(d.values()))\n",
    "        n = len(nums)\n",
    "        if check(dd):\n",
    "            return n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=nums[i]\n",
    "            d[x]-=1\n",
    "            c = d[x]\n",
    "            if c>0:\n",
    "                dd[c]+=1\n",
    "            dd[c+1]-=1\n",
    "            if dd[c+1]==0:\n",
    "                del dd[c+1]\n",
    "            if check(dd):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        num_freq = defaultdict(int)\n",
    "        freq_freq = defaultdict(int)\n",
    "        res = 1                                         #最短的就是1个数字的情况\n",
    "        species = 0                                     #数字种类数\n",
    "        max_freq = 0                                    #最大的频率\n",
    "        for i, x in enumerate(nums):\n",
    "            if num_freq[x] == 0:\n",
    "                species += 1\n",
    "            num_freq[x] += 1\n",
    "            max_freq = max(max_freq, num_freq[x])\n",
    "            freq_freq[num_freq[x]] += 1\n",
    "            freq_freq[num_freq[x] - 1] -= 1             #很容易忘记\n",
    "            \n",
    "            if species == i + 1 or species == 1:        # 123456 111111\n",
    "                res = i + 1\n",
    "            if freq_freq[max_freq] == species - 1 and freq_freq[1] == 1:    #111 222 333 4\n",
    "                res = i + 1\n",
    "            if freq_freq[max_freq] == 1 and freq_freq[max_freq - 1] == species - 1: #111 222 333 4444\n",
    "                res = i + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\r\n",
    "        freq = Counter(nums)\r\n",
    "        freq_cnt = Counter(freq.values())\r\n",
    "\r\n",
    "        def valid() -> bool:\r\n",
    "            if len(freq_cnt) > 2: return False\r\n",
    "            it = iter(freq_cnt.items())\r\n",
    "            if len(freq_cnt) == 1:\r\n",
    "                f, c = next(it)\r\n",
    "                return f == 1 or c == 1\r\n",
    "            f1, c1 = next(it)\r\n",
    "            f2, c2 = next(it)\r\n",
    "            return c1 == 1 and (f1 == 1 or f1 - f2 == 1) or \\\r\n",
    "                   c2 == 1 and (f2 == 1 or f2 - f1 == 1)\r\n",
    "        \r\n",
    "        def pop() -> None:\r\n",
    "            ele = next(tail)\r\n",
    "            freq_cnt[freq[ele]] -= 1\r\n",
    "            if freq_cnt[freq[ele]] == 0:\r\n",
    "                del freq_cnt[freq[ele]]\r\n",
    "            freq[ele] -= 1\r\n",
    "            if freq[ele] == 0:\r\n",
    "                del freq[ele]\r\n",
    "            else:\r\n",
    "                freq_cnt.setdefault(freq[ele], 0)\r\n",
    "                freq_cnt[freq[ele]] += 1\r\n",
    "        \r\n",
    "        res = len(nums)\r\n",
    "        tail = iter(reversed(nums))\r\n",
    "        while not valid():\r\n",
    "            res -= 1\r\n",
    "            pop()\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        num_fre_dict = {}\n",
    "        def isvalid(dic):\n",
    "            origin_fre_list = list(x for x in dic.values() if x)\n",
    "            fre_list = list(set(origin_fre_list))\n",
    "            print(fre_list, origin_fre_list)\n",
    "            if len(fre_list) == 2:\n",
    "                if abs(fre_list[0] - fre_list[1]) == 1 and origin_fre_list.count(max(fre_list[1],fre_list[0] )) == 1:\n",
    "                    return True\n",
    "                if 1 in fre_list and origin_fre_list.count(1) == 1:\n",
    "                    return True\n",
    "            if fre_list == [1] or len(origin_fre_list) == 1:\n",
    "                return True\n",
    "            return False\n",
    "        for i in nums:\n",
    "            num_fre_dict[i] = num_fre_dict.get(i,0) + 1\n",
    "        if isvalid(num_fre_dict):\n",
    "            return len(nums)\n",
    "        for j in range(len(nums)):\n",
    "            num_fre_dict[nums[len(nums)-1-j]] -= 1\n",
    "            if isvalid(num_fre_dict):\n",
    "                return len(nums) - j - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        freq, count = Counter(), Counter()\n",
    "        ans = maxFreq = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if count[num]:\n",
    "                freq[count[num]] -= 1\n",
    "            count[num] += 1\n",
    "            maxFreq = max(maxFreq, count[num])\n",
    "            freq[count[num]] += 1\n",
    "            if maxFreq == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 and freq[maxFreq] == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + 1 == i + 1 and freq[1] == 1:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        freq = Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            freq[cnt[num]] -= 1\n",
    "            if freq[cnt[num]] <= 0:\n",
    "                del freq[cnt[num]]\n",
    "            cnt[num] += 1\n",
    "            freq[cnt[num]] += 1\n",
    "            if len(freq) == 2:\n",
    "                s = sorted(freq.items())\n",
    "                if s[0][0] == 1 and s[0][1] == 1 or s[1][0] == s[0][0] + 1 and s[1][1] == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "            if len(freq) == 1:\n",
    "                s = sorted(freq.items())\n",
    "                if s[0][0] == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "                if len(cnt) == 1:\n",
    "                    ans = max(ans, i + 1)\n",
    "            # print(freq)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        cnt=collections.Counter()\n",
    "        freq=collections.defaultdict(int)\n",
    "        ans=1\n",
    "        species=0\n",
    "        maxfreq=0\n",
    "        for i,v in enumerate(nums):\n",
    "            cnt[v]+=1\n",
    "            if cnt[v]==1:\n",
    "                species+=1\n",
    "            maxfreq=max(maxfreq,cnt[v])\n",
    "            freq[cnt[v]] += 1\n",
    "            freq[cnt[v] - 1] -= 1   \n",
    "\n",
    "           #print(maxfreq,freq,cnt,nums[:i+1])\n",
    "            if species==i+1 or species==1:#12345678\n",
    "                ans=max(ans,i+1)\n",
    "               # print(nums[:i+1])\n",
    "            if  freq[maxfreq] ==species-1 and freq[1]==1 :  #1,1,1,2,2,2,3,3,3,4,4,4,5\n",
    "                ans=max(ans,i+1)\n",
    "             #   print(nums[:i+1])\n",
    "            if freq[maxfreq]==1 and freq[maxfreq-1]==species-1:\n",
    "                ans=max(ans,i+1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        freq, count = Counter(), Counter()\n",
    "        ans = maxFreq = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if count[num]:\n",
    "                freq[count[num]] -= 1\n",
    "            count[num] += 1\n",
    "            maxFreq = max(maxFreq, count[num])\n",
    "            freq[count[num]] += 1\n",
    "            if maxFreq == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 and freq[maxFreq] == 1 or \\\n",
    "               freq[maxFreq] * maxFreq + 1 == i + 1 and freq[1] == 1:\n",
    "                ans = max(ans, i + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEqualFreq(self, nums: List[int]) -> int:\n",
    "        mp_w_l = collections.defaultdict(lambda: 0)\n",
    "        mp_l_w = collections.defaultdict(set)\n",
    "        res = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            pre_cnt = mp_w_l[num]\n",
    "            mp_l_w[pre_cnt].discard(num)\n",
    "            if not mp_l_w[pre_cnt]:\n",
    "                del mp_l_w[pre_cnt]\n",
    "            mp_w_l[num] += 1\n",
    "            mp_l_w[pre_cnt + 1].add(num)\n",
    "\n",
    "            if len(mp_l_w) == 1:\n",
    "                if len(mp_l_w[pre_cnt + 1]) == 1:\n",
    "                    res = max(res, idx + 1)\n",
    "                if pre_cnt == 0:\n",
    "                    res = max(res, idx + 1)\n",
    "            elif len(mp_l_w) == 2:\n",
    "                if 1 in mp_l_w and len(mp_l_w[1]) == 1:\n",
    "                    res = max(res, idx + 1)\n",
    "                if pre_cnt in mp_l_w:\n",
    "                    if len(mp_l_w[pre_cnt + 1]) == 1:\n",
    "                        res = max(res, idx + 1)\n",
    "                if pre_cnt + 2 in mp_l_w:\n",
    "                    if len(mp_l_w[pre_cnt + 2]) == 1:\n",
    "                        res = max(res, idx + 1)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
